Conventionally, storage systems have stored transfer information transferred from a higher-level device (host) temporarily in cache memory, and then stored it in a storage device such as a hard disk. Recently, a technology has been proposed in which a storage system detects redundancy between transfer information and information already stored in a storage system, and transfer information determined as being redundant is not stored in a storage device. By preventing the storage system from storing such “redundant information” in the storage device, the physical storage capacity can be utilized effectively, and as a result the apparent storage capacity that the storage system shows to the host can be increased.
An example of such redundancy detection is described in U.S. Pat. No. 6,928,526. The storage system processes transfer information in units of segments and calculates the representative value and the feature value (hash mean) for data included in each segment. In addition, the storage system avoids writing identical information to the storage device by comparing the hash mean of the transfer information with the hash mean for the storage information stored in the storage device.
Meanwhile, another method of effectively utilizing storage capacity is data compression. In storage systems, algorithms that allow lossless compression are utilized. The LZ encoding algorithm. is a representative example of such algorithms.